package com.zdp.algorithm.stackandqueue;

import java.util.LinkedList;
import java.util.Scanner;
import java.util.Stack;

/**
 * @author Zhengdp
 * @date 2023年01月17日 11:15
 */
public class GetNum {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        GetNumImpl impl = new GetNumImpl();
        while(in.hasNextInt()) {
            int n = in.nextInt();
            int num = in.nextInt();
            int[] arr = new int[n];
            for(int i =0;i<n;i++) {
                arr[i] = in.nextInt();
            }
            System.out.println(impl.getNum(arr,num));
        }
    }
}

/**
 * 有两个关键点：
 * 1. 当数组 arr[left...right] 满足条件时，其子数组arr(left...right)都满足条件。
 *  这是因为子数组的最大值一定<=max , 最小值一定>=min ,所以 max1 - min1 < max - min < num
 * 2. 当数组arr[left...right] 不满足条件时，那么所有包含arr[left...right]的子数组都不满足条件
 *  包含arr[left...right]的子数组，其max1 >= max ,min1<=min, max1 - min1 > max -min > num
 *
 * 这题使用滑动窗口 + 单调队列 来解决。
 *  使用两个单调队列，用于记录当前滑动窗口中的最大值和最小值。
 *  问题的关键在于，如何滑动left 和 right。
 * 首先，固定left,滑动right ,right 滑动的前提是 arr[left,right]满足条件。
 *  当right不满足条件时，此时我们可以得知arr[left,right-1]是满足条件的，根据上面的特性，我们可以得到
 *   arr[left...right-1]的所有子数组都是满足条件的 ===> res = right - left;
 * 当right不满足条件，移动left ==> left和right的移动都需要更新 单调队列中的值
 * > 一般滑动窗口，都是固定左，然后移动右。只有当某个条件触发时，才会去停止右，移动左
 */
class GetNumImpl {
    public int getNum(int[] arr,int num) {
        int result = 0;
        int left = 0,right = 0;
        int length = arr.length;
        LinkedList<Integer> minQueue = new LinkedList<>();
        LinkedList<Integer> maxQueue = new LinkedList<>();
        while(left < length) {
            while(right < length) {
                if(minQueue.isEmpty() || minQueue.getLast() != right) {
                    pushMin(right,minQueue,arr);
                    pushMax(right,maxQueue,arr);
                }
                if(arr[maxQueue.getFirst()] - arr[minQueue.getFirst()] > num) {
                    break;
                }
                right ++;
            }
            result += right - left;
            if(minQueue.getFirst() == left) {
                minQueue.removeFirst();
            }
            if(maxQueue.getFirst() == left) {
                maxQueue.removeFirst();
            }
            left ++;
        }
        return result;
    }

    private void pushMin(int index,LinkedList<Integer> minQueue,int[] arr) {
        while(!minQueue.isEmpty() && arr[minQueue.getLast()] >= arr[index]) {
            minQueue.removeLast();
        }
        minQueue.addLast(index);
    }

    private void pushMax(int index,LinkedList<Integer> maxQueue,int[] arr) {
        while(!maxQueue.isEmpty() && arr[maxQueue.getLast()] <= arr[index]) {
            maxQueue.removeLast();
        }
        maxQueue.addLast(index);
    }
}
